package com.example.easyscript.bean.task;

import com.example.easyscript.common.util.MapUtil;
import com.example.easyscript.dto.MyPair;
import lombok.Data;

import java.util.*;

/**
 * 临接矩阵
 */
@Data
public class AdjacencyMatrix {
    private List<Integer> status;

    //临界表
    private Map<Integer, HashSet> matrix;

    //结果缓存
    private Map<Integer, Map<Integer, Integer>> answerCache;

    //边
    private List<MyPair<Integer, Integer>> entrance;

    public AdjacencyMatrix(List<Integer> status, List<MyPair<Integer, Integer>> entrance) {
        matrix = MapUtil.getMap(status, new HashSet<Integer>(), HashSet.class);
        answerCache = new HashMap<>();
        this.status = status;
        this.entrance = entrance;
        //初始化临接表
        entrance.forEach(item -> {
            Set<Integer> buf = matrix.get(item.getKey());
            buf.add(item.getValue());
        });
    }

    //迪杰斯拉最短路径算法
    public Map<Integer, Integer> dijkstra(Integer startOrder) {
        if (answerCache.containsKey(startOrder)) {
            //如果已经有了以该起点拓展的djs 就不用再算一次了。
            return answerCache.get(startOrder);
        }

        //路径都初始化为不可达
        Map<Integer, Integer> pathMap = MapUtil.getMap(status, new Integer(-1), Integer.class);
        //是否有被访问,初始化为全部没有访问
        Map<Integer, Boolean> visit = MapUtil.getMap(status, false, Boolean.class);
        //优先队列
        PriorityQueue<MyPair<Integer, Integer>> selector = new PriorityQueue<>(((o1, o2) -> {
            return o1.getValue() - o2.getValue();
        }));
        //花销
        Map<Integer, Integer> cost = MapUtil.getMap(status, Integer.MAX_VALUE, Integer.class);

        Set<Integer> startSet = matrix.get(startOrder);

        //初始化
        visit.put(startOrder, true);
        for (Integer point : status) {
            int value = Integer.MAX_VALUE;
            if (!point.equals(startOrder)) {
                if (startSet.contains(point)) {
                    //将起点可达的点标记为1
                    value = 1;
                    //将他们的上一个定点标记为起点
                    pathMap.put(point, startOrder);
                    cost.put(point, 1);
                }
            }
            selector.add(new MyPair<>(point, value));
        }

        //开始计算
        for (int i = 0; i < status.size() - 1; i++) {
            //使用优先队列优化,取出当前最小可达路径
            MyPair<Integer, Integer> poll = null;
            do {
                poll = selector.poll();
            } while (!visit.isEmpty() && visit.get(poll.getKey()));
            int index = poll.getKey();
            int dist = poll.getValue();
            if (Integer.MAX_VALUE == dist) {
                continue;
            }
            //将当前点表标记为 已经遍历过
            visit.put(index, true);
            Set<Integer> indexSet = matrix.get(index);
            for (Integer nextPoint : status) {
                //开始枚举
                if (nextPoint.equals(index) || nextPoint.equals(startOrder)) {
                    //跳过自己和起点
                    continue;
                }
                //起点到当前点的距离
                int currentDist = cost.get(nextPoint);
                if (indexSet.contains(nextPoint) && currentDist > dist + 1) {
                    //如果起点到当前点的距离大于起点到index的距离+1则更新距离
                    cost.put(nextPoint, dist + 1);
                    //更新优先队列
                    selector.add(new MyPair<>(nextPoint, dist + 1));
                    //更新路径
                    pathMap.put(nextPoint, index);
                }
            }
        }
        answerCache.put(startOrder, pathMap);
        return pathMap;
    }

    public Integer getNextOrder(Integer start, Integer end) {
        Map<Integer, Integer> answer = dijkstra(start);
        int pid = end;
        while (true) {
            Integer before = answer.get(pid);
            if (before == -1) {
                throw new RuntimeException("不可達！");
            }
            if (before.equals(start)) {
                return pid;
            }
            pid = before;
        }
    }
}
